/**
 * 广度优先搜索BFS
 * 2018年 12月 14日 星期五
 *
 * @author fireway
 */
class Vertex {
    public char mLabel;

    public boolean mWasVisited;

    public Vertex(char lab) {
        mLabel = lab;
        mWasVisited = false;
    }
}

class Queue {
    private final int SIZE = 20;
    private int[] mQueArray;
    private int mFront;
    private int mRear;

    public Queue() {
        mQueArray = new int[SIZE];
        mFront = 0;
        mRear = -1;
    }

    public void insert(int v) {
        if (mRear == SIZE - 1) {
            mRear = -1;
        }
        mQueArray[++mRear] = v;
    }

    public int remove() {
        int temp = mQueArray[mFront++];
        if (mFront == SIZE) {
            mFront = 0;
        }
        return temp;
    }

    public boolean isEmpty() {
        return (mRear + 1 == mFront || (mFront + SIZE - 1 == mRear));
    }
}

/**
 * 无向图
 */
class Graph {
    private final int MAX_VERTS = 20;
    // 顶点对象放在数组中维护
    private Vertex[] mVertexList;

    private int[][] mAdjMat;
    // 当前顶点的个数
    private int mVertNum;

    private Queue mQueue;

    public Graph() {
        mVertNum = 0;
        mVertexList = new Vertex[MAX_VERTS];
        // adjacency matrix - 邻接矩阵
        mAdjMat = new int[MAX_VERTS][MAX_VERTS];
        for (int i = 0; i < MAX_VERTS; i++) {
            for (int j = 0; j < MAX_VERTS; j++) {
                mAdjMat[i][j] = 0;
            }
        }
        mQueue = new Queue();
    }

    /**
     * 添加顶点
     */
    public void addVertex(char lab) {
        mVertexList[mVertNum++] = new Vertex(lab);
    }

    /**
     * 添加边
     */
    public void addEdge(int start, int end) {
        mAdjMat[start][end] = 1;
        mAdjMat[end][start] = 1;
    }

    /**
     * 显示顶点
     *
     * @param v
     */
    public void displayVertex(int v) {
        System.out.print(mVertexList[v].mLabel);
    }

    /**
     * <p>
     * 深度优先搜索的关键在于能够找到与某一个顶点邻接且没有访问过的顶点
     * </p>
     *
     * @param j
     * @return
     */
    public int getAdjUnvisitedVertex(int j) {
        for (int i = 0; i < mVertNum; i++) {
            if (mAdjMat[j][i] == 1 && !mVertexList[i].mWasVisited) {
                return i;
            }
        }
        return -1;
    }

    public void bfs() {
        displayVertex(0);
        mQueue.insert(0);
        mVertexList[0].mWasVisited = true;
        int v2 = -1;

        while (!mQueue.isEmpty()) {
            // remove vertex at head
            int v1 = mQueue.remove();
            // until it has no unvisited neighbors
            while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                // 1. display it
                displayVertex(v2);
                // 2. insert it
                mQueue.insert(v2);
                // 3. mark it
                mVertexList[v2].mWasVisited = true;
            }
        }

        // 在bfs()方法的最后，重置了所有mWasVisited标记位，这样就可以在稍后继续使用bfs()方法
        // 队列此时为空，所以不需要重置。
        for (int i = 0; i < mVertNum; i++) {
            mVertexList[i].mWasVisited = false;
        }
    }
}

